<?php
class MergeSort
{
    /**
     * 将数组两个有序部分合并成一个
     * @param $arr
     * @param $left
     * @param $mid
     * @param $right
     * @return mixed
     */
    private function twoMergeSort($arr,$left,$mid,$right){
        $aIndex = $left==$mid ? -1 : $left;
        $bIndex = $mid==$right ? -1 : $mid;
        $crr = [];

        while (($aIndex >= $left && $aIndex < $mid) || ($bIndex >= $mid && $bIndex <= $right)){
            $aValue = $arr[$aIndex]??null;
            $bValue = $arr[$bIndex]??null;
            if(($aIndex < $left || $aIndex >= $mid) || ($bValue < $aValue && $bValue != null)){
                $crr[] = $bValue;
                $bIndex++;
            }else{
                $crr[] = $aValue;
                $aIndex++;
            }
        }

        for ($i = 0;$i < ($right - $left);$i++){
            $arr[$i+$left] = $crr[$i];
        }
        return $arr;
    }


    public function arrayMergeSort($arr){
      $this->recursionMergeSort($arr,0,count($arr) - 1);
        return $arr;
    }

    private function recursionMergeSort($arr,$left,$right){
        if($left == $right){
            return;
        }

        $mid = ceil((($right - $left)/2) + $left);//($right + $left)/2 这种考虑内存溢出的优化

        $arr = $this->recursionMergeSort($arr,$left,$mid-1); //递归思想，交给下层处理排序
        $arr = $this->recursionMergeSort($arr,$mid,$right);//递归思想，交给下层处理排序
        $arr = $this->twoMergeSort($arr,$left,$mid,$right);//merge 两部有序内容
        return $arr;

    }
}